我站原创视频教程，网上视频教程学校，仅需要一个耳机+远程即可完成所有教学任务。

题 目:数据结构 双向链表(副堆栈)的实现

双向链表的好处是可以快速地随便添加和删除而时间为常数
两头为o(3)
中间为o(4)
数组却为o(length-index) length为数组的长度，index为添加和删除的位置
用法：
import fl.util.LnkList;
var link:LinkList = new LinkList([2,3,4,5]);
link.unshift(1);
trace(link.toString());
link.addItem(3,12);
trace(link.join("\n"));
错误 class:
class fl.lang.ClsError extends Error {
var cls:String;
function ClsError(_cls:String, msg:String) {
cls = _cls;
message = msg;
}
function toString() {
return (name+":\n\tclass : "+cls+"\n\tmessage : "+message);
}
}
堆栈 class:
import fl.lang.ClsError;
class fl.util.Stack extends fl.Obj {
private var data:Array;
//数据
private var right:Number;
//MAX指针
public function get length() {
//堆栈的长度
return (right);
}
public function clone():Stack {
var result:Array = data.slice(0, right);
return new Stack(result);
}
public function Stack(arr:Array) {
//构造函数 ，arr :一个1维数组
data = new Array();
if (arr) {
data = arr.slice();
right = arr.length-1;
return;
}
right = 0;
}
public function search(key:Object):Boolean {
for (var i = 0; i<right; i++) {
if (data[i] == key) {
return true;
}
}
return false;
}
public function init():Void {
//初始化
data.splice(0);
right = 0;
}
public function get isEmpty():Boolean {
//判断是否为空
if (right == 0) {
return (true);
}
return (false);
}
public function push(obj:Object):Void {
//入栈
data.push(obj);
right ++;
}
public function pop():Object {
//出栈
if (!isEmpty) {
right--;
return (data[right]);
}
throw new ClsError("Stack", "pop is empty");
}
public function getTop():Object {
//返回顶端
return (data[right]);
}
public function dispose():Void {
//释放内存
data.splice(right);
}
public function trace():Void {
//打印堆栈
trace("Trace Stack-----");
for (var i = 0; i<right; i++) {
trace("\tItem "+i+" : "+data[i]);
}
trace("/Trace Stack");
}
}
双向链表class:
/*************************************************************************
*双向链表
*v 1.0
*player 7
*2006/1/2
/************************************************************************/
import fl.lang.ClsError;
import fl.util.Stack;
class fl.util.LinkList extends fl.Obj {
/*
*存放数据
*data[i]={value:数据， next:右指针， previous:左指针}
*data[0].last=null
*data[max].next=null
*/
private var data:Array;
private var closeList:Stack; //已删除的下标的集合
private var first:Number; //开始指针
private var last:Number; //结束指针
private var _length:Number; //链表的长度
public function get length():Number {
return _length;
}
/*
*构造函数
*LinkList(一个1维数组)
*LinkList()
*/
public function LinkList(arr:Array) {
closeList = new Stack();
data = new Array();
if (arr) { //LinkList(一个1维数组)
var arrLen:Number = arr.length;
for (var i:Number = 0; i < arrLen; i++) {
data.push({value:arr[i], next:i + 1, previous:i - 1});
}
first = 0;
last = arrLen - 1;
data[first].previous = null;
data[last].next = null;
_length = arrLen;
return;
}
//LinkList()
first = last = 0;
}
/*
*得到index处的值
*get(index)
*/
public function get(index:Number):Object {
if (index >= _length || index < 0) {
throw new ClsError("LinkList", "get index is outside");
}
var pos:Number = find(index);
return data[pos].value;
}
/*
*设置index处的值
*set(index,value)
*/
public function set(index:Number, value:Object):Void {
if (index < 0) {
throw new ClsError("LinkList", "set index is outside");
}
//当超界时
if (index >= _length) {
var len:Number = index - _length + 2;
var pos:Number = last;
for (var i:Number = 1; i < len; i++) {
data[i + pos] = {value:undefined, next:i + pos + 1, previous:i + pos - 1};
}
data[index].value = value;
data[index].next = null;
data[last].next = _length;
last = index;
_length = index + 1;
return;
}
var pos:Number = find(index);
data[pos].value = value;
}
/*
*出栈
*pop()
*/
public function pop():Object {
if (_length == 0) {
//当链表为空时
throw new ClsError("LinkList", "pop this is empty");
}
//不为空时
try {
return data[last].value;
} finally {
closeList.push(last);
last = data[last].previous;
_length--;
}
}
/*
*入栈
*pop()
*/
public function push(value:Object):Void {
var pos:Number = getPos();
data[pos] = {value:value, next:null};
data[pos].previous = last;
data[last].next = pos;
last = pos;
_length++;
}
/*
*从头插入
*shift()
*/
public function shift():Object {
if (_length == 0) {
//当链表为空时
throw new ClsError("LinkList", "shift this is empty");
}
//不为空时
try {
return data[first].value;
} finally {
closeList.push(first);
first = data[first].next;
_length--;
}
}
/*
*从头删除
*unshift()
*/
public function unshift(value:Object):Void {
var pos:Number = getPos();
data[pos] = {value:value, previous:null};
data[pos].next = first;
data[first].previous = pos;
first = pos;
_length ++;
}
/*
*查找一个对象
*search()
*/
public function search(key:Object):Boolean {
var pos:Number = first;
var i:Number = _length;
while (-- i) {
if(data[pos].value == key) {
return true;
}
pos = data[pos].next;
}
return false;
}
/*
*在index增加一个值
*addItem(index, value)
*/
public function addItem(index:Number, value:Object):Void {
if (!index) throw new ClsError("LinkList", "addItem index is null");
var pos:Number = find(index);
switch (pos) {
case first :
unshift(value);
break;
case last :
push(value);
break;
default :
var newPos:Number;
try {
newPos = Number(closeList.pop());
} catch (e) {
newPos = data.length;
}
data[newPos] = {value:value, previous:pos, next:data[pos].next};
data[pos].next = newPos;
data[data[newPos].next].previous=newPos
_length ++;
}
}
/*
*在index删除一个值
*removeItem(index)
*/
public function removeItem(index:Number):Void {
if (!_length) throw new ClsError("LinkList", "removeItem this is empty");
if (!index) throw new ClsError("LinkList", "removeItem index is null");
var pos:Number = find(index);
switch (pos) {
case first :
pop();
break;
case last :
shift();
break;
default :
var previous:Number = data[pos].previous;
var next:Number = data[pos].next;
data[previous].next = next;
data[next].previous = previous;
closeList.push(pos);
_length --;
}
}
/*
*从index开始，向后查找
*indexOf(key,index)
*/
public function indexOf(key:Object,index:Number):Number {
if (!key) throw new ClsError("LinkList", "indexOf key is null");
if (!index) index = 0;
var pos:Number = first;
for (var i:Number = 0; i < index; i++) {
pos = data[pos].next;
}
for (var i:Number=_length-index; i>0; i--) {
if(key == data[pos].value) return pos;
pos = data[pos].next;
}
}
/*
*从index开始，向前查找
*lastIndexOf(key,index)
*/
public function lastIndexOf(key:Object,index:Number):Number {
if (!key) throw new ClsError("LinkList", "lastIndexOf key is null");
if (!index) index = 0;
var pos:Number = last;
for (var i:Number = 0; i < index; i++) {
pos = data[pos].previous;
}
for (var i:Number=_length-index; i>0; i--) {
if(key == data[pos].value) return pos;
pos = data[pos].previous;
}
}
//克隆
public function clone():LinkList {
var result:LinkList=new LinkList();
var pos:Number=first
for (var i=0; i<_length; i++) {
result.push(data[pos].value);
pos=data[pos].next;
}
return result;
}
public function toString():String {
return toArray().toString();
}
public function join(separator:String):String {
return toArray().join(separator);
}
public function toArray():Array {
var result:Array = new Array();
var pos:Number = first;
var i:Number = _length;
while (--i) {
result.push(data[pos].value);
pos = data[pos].next;
}
return result;
}
//得到一个空地址
private function getPos():Number {
var result:Number
try { result = Number(closeList.pop()); }
catch (e) { result = data.length; }
return result;
}
//得到第index的下标
private function find(index:Number):Number {
var pos:Number;
if (index > _length / 2) {
//从后向前
var pos = last;
for (var i:Number = _length - index - 1; i > 0; i--) {
pos = data[pos].previous;
}
}else{
//从前向后
var pos = first;
for (var i:Number = 0; i < index; i++) {
pos = data[pos].next;
}
}
return pos;
}
}

省级FLASH课件制作培训请加我站管理QQ444860709 培训QQ专业群67042004。

FLASH8.0教程→ flash cs3视频教程 flashcs3教程 flash cs3教程下载 flashcs3视频教程 flash cs3 pro教程 flash cs3教程网 flash cs3 实例教程 flashcs3教程下载 flash cs3教程 pdf flash cs3按钮教程